# -*- coding:utf-8 -*-

"""
题目描述
对于斐波拉契经典问题，我们都非常熟悉，通过递推公式F(n) = F(n - 1) + F(n - 2)，我们可以在线性时间内求出第n项F(n)，现在考虑斐波拉契的加强版，我们要求的项数n的范围为int范围内的非负整数，请设计一个高效算法，计算第n项F(n-1)。第一个斐波拉契数为F(0) = 1。
给定一个非负整数，请返回斐波拉契数列的第n项，为了防止溢出，请将结果Mod 1000000007。
测试样例：
3
返回：
2

题目解析：
下列推算中还是没有指出为什么代码中需要一个subplot矩阵，还没有弄明白这里

F(n)        F(n - 1)
F(n - 1)    F(n - 2)

=

拆分 为两个矩阵相乘

1   1       F(n - 1)    F(n - 2)
        *
1   0       F(n - 2)    F(n - 3)


依次类推
可以求出

n 个
1   1       F(1)    F(0)
        *
1   0       F(0)    F(-1)

假设矩阵
1   1

1   0
为 basic 矩阵，n - 2 等于 13
所以，此时可表示为
basic ^ 13
13 的二进制为 1011
所以
basic ^ 13 = basic ^ 8 * basic ^ 4 * basic ^ 1
即可通过二进制进行求解，每次都判断余数
"""

class Fibonacci:
    def getNthNumber(self, n):
        # write code here
        res = [[1, 1], [1, 0]] # 累乘的矩阵
        subplot = [[1, 0], [0, 1]] # 剩余项
        while n > 1:
            if n & 1: # 如果除以2的余数不为0的时候，要乘以剩余项
                subplot = self.mutiply(res, subplot)
            res = self.mutiply(res, res)
            n = n >> 1
        res = self.mutiply(res, subplot)
        return res[0][0] % 1000000007
    
    def mutiply(self, a, b):
        temp = [[0, 0], [0, 0]]
        for i in range(len(a)):
            for j in range(len(b)):
                for k in range(len(temp)):
                    temp[i][j] += a[i][k] % 1000000007 * b[k][j] % 1000000007
        
        return temp

if __name__ == "__main__":
    fib = Fibonacci()
    print fib.getNthNumber(12)
    print fib.getNthNumber(3)